Subspace embedding from Johnson-Lindenstrauss

Let $\mathcal{U} \subset \mathbb{R}^n$ be a $d$-dimensional linear subspace in $\mathbb{R}^n$. If $\mathbf{\Pi} \in \mathbb{R}^{m \times d}$ is chosen from any distribution $\mathcal{D}$ satisfying the Distributional JL Lemma, then with probability $1-\delta$, $$(1-\epsilon)||\mathbf{v}||_2^2 \leq ||\mathbf{\Pi v}||_2^2 \leq (1+\epsilon)||\mathbf{v}||_2^2$$ for all $\mathbf{v} \in \mathcal{U}$, as long as $m=O \left(\frac{d\log(1/\epsilon)+\log(1/\delta)}{\epsilon^2} \right)$.¹

Corollary

If we choose $\mathbf{\Pi}$ and properly scale, then with $O(d/\epsilon^2)$ rows, #incomplete